409. 最长回文串

Similar Question

Solution Tips

方案一: 贪心算法

回文串是一个正读和反读都一样的字符串。对一个左边的字符 i 右边一定会有一个对称 i。比如 'abcba'， 'aa'，'bb' 这几个回文串。其中第一个有点特殊，中间的 c 是唯一的。

对于每个字母，假设它出现了 v 次。我们可以让 v \ 2 * 2 个字母左右对称。例如，对于字符串 'aaaaa'，其中 'aaaa' 是左右对称，其长度为 5 \ 2 * 2 = 4。

最后，如果有任何一个满足 v % 2 == 1 的 v，那么这个字符就可能是回文串中唯一的那个中心。针对这种情况，我们需要判断 v % 2 == 1 && ans % 2 == 0，后面的判断主要是为了防止重复计算。

实现

  var longestPalindrome = function(s) {
    const len = s.length
    const map = {}
    let ans = 0
    for (let i = 0; i < len; i++) {
      if(map[s[i]]===undefined){
        map[s[i]] = 1
      }else{
        map[s[i]]++
      }
    }
    for (const count of Object.values(map)) {
      ans += (count>>>1)*2
      // 中心只能选择一次，之后ans % 2 !== 0, 相当于是只选择了最先遇到的奇数字符为中心
      if (count % 2 == 1 && ans % 2 == 0) ans++
    }
    return ans
  }
  
  console.log(longestPalindrome('aabbbccc'))